#include <stdio.h>
#include <stdlib.h>
#include <csp_spu.h>
#include <csp_debug.h>

/*
 * Test must:
 * 	1) Build a stack
 * 	2) Use globale initialized (.data)
 * 	3) Remember changed values after a yield
 */
int global_pid;

void quick(int *left, int *right) {
	int pid = csp_pid();
	if (right > left) {
		int pivot = left[(right-left)/2];

		int *r = right, *l = left;
		do {
			while (*l < pivot) l++;
			while (*r > pivot) r--;
			if (l <= r) {
				int t = *l;
				*l++ = *r;
				*r-- = t;
			}
		} while (l <= r);
		csp_yield();

	ASSERT( pid == csp_pid() );
	ASSERT( global_pid == csp_pid() );

		quick(left, r);
		quick(l, right);
	}
}
void sort(int *array, int length)
{
	quick(array, array+length-1);
}

int Run(){
	int i, val;
	int pid = csp_pid();
	global_pid = csp_pid();


	int data[] = {99709, 99462, 96693, 92288, 86874, 85706, 84015, 82253, 81564, 74659, 
		72842, 70461, 68757, 66214, 61333, 61087, 58349, 57418, 54551, 49540, 
		49126, 48473, 46571, 46368, 45743, 44396, 44140, 44069, 43074, 42599, 
		39799, 37928, 37654, 37536, 37148, 35834, 34427, 33850, 32376, 30871, 
		27594, 21602, 21078, 17203, 16430, 13009, 11127, 3706, 3174, 721};

	PRINTF_FOR_TESTING("quicksort_task starting on spe #%i with pid %i\n", csp_spe_id(), pid);
	val = 100000;
	//PRINTF_FOR_TESTING("Before quick sort: ");
	for(i = 0; i < 50; i++){
		ASSERT( val > data[i] );
		val = data[i];
		//PRINTF_FOR_TESTING("%i ", data[i]);
	}
	//PRINTF_FOR_TESTING("\n");
	

	sort(data, 50);

	val = -1;
	//PRINTF_FOR_TESTING("After quick sort: ");
	for(i = 0; i < 50; i++){
		ASSERT( val < data[i] );
		val = data[i];
		//PRINTF_FOR_TESTING("%i ", data[i]);
	}
	//PRINTF_FOR_TESTING("\n");
	
	ASSERT( pid == csp_pid() );
	ASSERT( global_pid == csp_pid() );

	PRINTF_FOR_TESTING("quicksort_task terminating on spe #%i with pid %i\n", csp_spe_id(), pid);
	return 3399;
}

